package cn.edu.xjtu.carlWay.linkedList.reverseLinkedList;

import cn.edu.xjtu.Util.ListNode.ListNode;
import cn.edu.xjtu.Util.ListNode.ListNodeUtil;

/**
 * 206. 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = ListNodeUtil.generate(nums);
        ListNodeUtil.print(head);
        ListNode newHead = reverseList(head);
        ListNodeUtil.print(newHead);
    }

    /**
     * 递归方法
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode newHead = new ListNode();
        reverse(head, newHead);
        head.next = null;
        return newHead.next;
    }

    public static ListNode reverse(ListNode node, ListNode newHead) {
        if (node.next == null) {
            newHead.next = node;
            return node;
        }
        ListNode preNode = reverse(node.next, newHead);
        preNode.next = node;
        return node;
    }

    /**
     * 迭代方法
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode newHead = head;
        ListNode node = head.next;
        while (node != null) {
            ListNode temp = newHead;
            newHead = new ListNode(node.val, temp);
            node = node.next;
        }
        head.next = null;
        return newHead;
    }
}


